

/*
 * Timothy Ginder
 * TCSS 343 - Spring 2013
 * Homework 5 : Problem 1
 */

/**
 * This program finds the longest ascending subsequence in n^2 time.
 * @author Timothy Ginder (tginder@uw.edu)
 * @version 25 May 2013
 */

public class HW_5_1 {

	/**
	 * Main method. 
	 * @param args Not used
	 */
	public static void main(String[] args) {
		
		String[] hello = new String[6];
		hello[0] = "10";
		hello[1] = "21";
		hello[2] = "11";
		hello[3] = "06";
		hello[4] = "66";
		hello[5] = "12";
		
		int longestSequence =  LongestAscendingSubsequence(hello);
		System.out.println("The longest ascending sequnce in the string is: " + longestSequence);

	}

	//We were required to use dynamic programming to find the longest ascending subsequence problem. The subsequence may be and may be not consecutive. Please implement your algorithm using Java in the following function. Note: we use two characters to represent one number within 0~99. For example, string 0718 represents two numbers 7 and 18.
	public static int LongestAscendingSubsequence(String[] unorderedInput)
	{
		//String[] orderedInput = new String[]();
		String[] orderedInput = MergeSort(unorderedInput, 0, unorderedInput.length);
		return LongestCommonSubsequence(unorderedInput, orderedInput);	
	}
	public static String[] MergeSort(String[] unorderedInput, int first, int n)
	{
		String[] ordered = new String[unorderedInput.length];
				ordered = unorderedInput;
		   int n1 = 0;
		    int n2 = 0;

		    if(n > 1) {
		        n1 = n/2;
		        n2 = n-n1;
		        
		        MergeSort(ordered, first, n1);
		        MergeSort(ordered, first + n1, n2);
		    }

		   return Merge(ordered, first, n1, n2);
	}
	
	public static String[] Merge(String[] data, int first, int n1, int n2) {
		String[] temp = new String[n1 + n2];
        int copied = 0, copied1 = 0, copied2 = 0;

        while ((copied1 < n1) && (copied2 < n2))
        {
            if (data[first + copied1].compareTo(data[first + n1 + copied2]) < 0)
                temp[copied++] = data[first + (copied1++)];
            else
                temp[copied++] = data[first + n1 + (copied2++)];
        }

        while (copied1 < n1)
            temp[copied++] = data[first + (copied1++)];
        while (copied2 < n2)
            temp[copied++] = data[first + n1 + (copied2++)];

        for (int i = 0; i < copied; i++)
            data[first + i] = temp[i];
		return data;
	}
	
	public static int LongestCommonSubsequence(String A[], String B[])
	{
	    int maxLen = 0;
	    for (int a = 0; a < A.length; a++) {
	        for (int b = 0; b < B.length; b++) {
	            String first = A[a];
	            String second = B[b];
	            if (first == null || second == null || first.length() == 0 || second.length() == 0) {
	                return 0;
	            }
	         
	            int fl = first.length();
	            int sl = second.length();
	            int[][] table = new int[fl][sl];
	         
	            for (int i = 0; i < fl; i++) {
	                for (int j = 0; j < sl; j++) {
	                    if (first.charAt(i) == second.charAt(j)) {
	                        if (i == 0 || j == 0) {
	                            table[i][j] = 1;
	                        }
	                        else {
	                            table[i][j] = table[i - 1][j - 1] + 1;
	                        }
	                        if (table[i][j] > maxLen) {
	                            maxLen = table[i][j];
	                        }
	                        System.out.println(table[i][j]);
	                    }
	                }
	            }
	        }
	    }
	    return maxLen;
	}
}